#include "sort.h"

void _MergeSort(vector<int>& vc, int begin, int end, vector<int>& tmp);

//void MergeSort(vector<int>& vc){
//  vector<int> tmp;
//  tmp.resize(vc.size());
//  _MergeSort(vc, 0, vc.size(), tmp);
//}

void MergeSort(vector<int>& vc){
  vector<int> tmp;
  tmp.resize(vc.size());
  size_t gap = 1;
  while(gap < vc.size())
  {
    for(size_t i = 0; i<vc.size(); i+=2*gap)
    {
      size_t begin1 = i;
      size_t end1 = begin1+gap;
      size_t begin2 = i+gap;
      size_t end2 = begin2+gap;

      size_t j = begin1;
      if(end1 > vc.size())
      {
        end1 = vc.size();
        while(end1-begin1 > 1)
        {
          tmp[j++] = vc[begin1++];
        }
        continue;
      }

      if(end2 > vc.size())
      {
        end2 = vc.size();
      }
      
      while(end1-begin1 > 0 && end2-begin2 >0)
      {
        if(vc[begin1] <= vc[begin2])
        {
          tmp[j++] = vc[begin1++];
        }
        else{
          tmp[j++] = vc[begin2++];
        }
      }
      while(end1-begin1 > 0)
      {
        tmp[j++] = vc[begin1++];
      }
      while(end2-begin2 > 0)
      {
        tmp[j++] = vc[begin2++];
      }
    }
    
    for(size_t i = 0; i<vc.size(); ++i)
    {
      vc[i] = tmp[i];
    }
    gap *= 2;
  }
}

void _MergeSort(vector<int>& vc, int begin, int end, vector<int>& tmp){
  int midi = begin+(end-begin)/2;
  int begin1 = begin;
  int end1 = midi;
  int begin2 = midi;
  int end2 = end;
  
  if(end1-begin1>1)
  {
    _MergeSort(vc, begin1, end1, tmp);
  }
  if(end2-begin2>1)
  {
    _MergeSort(vc, begin2, end2, tmp);
  }

  int i = begin;
  while(end1-begin1 > 0 && end2-begin2 > 0)
  {
    if(vc[begin1] <= vc[begin2])
    {
      tmp[i++] = vc[begin1++];
    }
    else{
      tmp[i++] = vc[begin2++];
    }
  } 
  while(end1-begin1 > 0)
  {
    tmp[i++] = vc[begin1++];
  }
  while(end2-begin2 > 0)
  {
    tmp[i++] = vc[begin2++];
  }

  for(int j = begin; j<end; ++j)
  {
    vc[j] = tmp[j];
  }

}
